Networks of computer systems are ubiquitous in our society and such networks range in size from two-computer local area networks to wide area networks which include thousands of computers and which span the entire world. It is frequently desirable to send a message to many other computers of a computer network.
Multicasting is a mechanism by which a relatively low number of messages can be used to convey a message to many computers of a computer network. Consider, for example, computer network 100 shown in FIG. 1. Suppose computer 102A has a message to send to all computers 102B-Y of computer network 100. Through multicast, computer 102A forms a single copy of the message and sends the message to computers 102B-D to which computer 102A is directly coupled through computer network 100 as shown. Computer 102D recognizes the message as multicast and forms additional copies to send to computers 102E-H, to which computer 102D is directly coupled through computer network 102D as shown. Similarly, computer 102H forwards copies of the message to computers 102J-L, and the message is propagated through computer network 100 to all of computers 102B-Y.
Unicast is a messaging protocol in which each message has an intended recipient. Using unicast to send a message from computer 102A to computers 102B-Y involves twenty-two separate messages transmitted through the portion of computer network 100 between computers 102A and 102D. By comparison, multicast transmits a single message through that portion of computer network 100. The efficiency of multicast relative to unicast is relatively modest in this illustrative example in comparison to multicast messages through wide-area networks which include thousands of computers.
It is frequently desirable to send messages to a local portion of a wide-area network. Messages therefore include a time-to-live (TTL) parameter which establishes a condition for expiration of a multicast message. The TL parameter of a multicast message is initialized by the sending computer and is decreased by each computer which forwards the multicast message. In some networks, the TTL parameter of a multicast message is decremented, i.e., decreased by one, by each computer which forwards the message such that the TTL parameter specifies an expiration condition in terms of network hops. In other networks, each computer which forwards a message decreases the TTL parameter of the message by an amount of time required to transfer the message to the computer such that the TTL parameter specifies an expiration condition in terms of an amount of time the message is permitted to travel. Some of the latter networks require that each computer decrease the TTL parameter by at least one second such that the TTL parameter specifies an expiration condition in terms of a combination of a maximum number of network hops and a maximum amount of time. When the TTL parameter of a multicast message is decreased below a predetermined threshold, which is typically zero, the multicast message is destroyed. The following example is illustrative.
Suppose computer 102A wishes to send a multicast message to computers 102B-G. Computer 102A can form a multicast message with a TTL parameter whose value is two. The message reaches computers 102B-D since computers 102B-D are coupled directly to computer 102A, through computer network 100. Computer 102D decrements the TTL parameter of the message to have a value of one and forwards the multicast message to computers 102E-H. Thus, computers 102B-G receive the multicast message. In addition, computer 102H receives the multicast message. Computer 102H decrements the TTL parameter of the multicast message to have a value of zero. Accordingly, computer 102H destroys the multicast message. As a result, the multicast message does not pass beyond computer 102H and does not unnecessarily burden the remainder of computer network 100.
To determine what value to which to set the TTL parameter of a particular multicast message, each computer of a computer network generally includes a database in which the distance to each other computer of the computer network in terms of TTL parameter values are stored. Such a distance is referred to as a TTL distance. To populate such a database, a computer of a computer network must generally be capable of determining such TTL distances. In computer networks in which header information of messages can be directly examined, such determination is a matter of comparing the difference between the initial and current values of the TTL parameter of messages from specific computers. However, initial TTL parameters of received messages are generally not stored in the header of such messages and, in a number of computer network environments, current TTL parameter values are not accessible.
One mechanism for determining TTL distances between computers of a computer network when current TTL parameter values cannot be directly examined is called an expanding ring search. In general, a multicast message with a TTL parameter whose value is one is sent through the computer network. All computers which respond are determined to have a TTL distance of one. Next, a multicast message with a TTL parameter whose value is two is sent through the computer network. All computers which respond are determined to have a TTL distance of two. Multicast messages with ever increasing TTL parameter values are sent and responses from such multicast messages are gathered to determine the TTL distances of all computers of the computer network.
Expanding ring search suffers from some disadvantages. First, expanding ring search is slow. In general, each computer of the computer network must respond to each multicast message before the next multicast message can be sent. In addition, the computer which sent the original multicast message determines that all computers have responded by waiting a predetermined amount of time. Such a predetermined amount of time can be several seconds in duration, and a complete expanding ring search can include several hundred multicast messages. As a result, determination of TTL distances using expanding ring search can take several minutes.
The second disadvantage of expanding ring searches is that such places a substantial burden on the computer network in terms of message traffic. Specifically, each computer of the computer network responds to each and every multicast message received. In a computer network which includes thousands of computers, each of several hundred multicast messages can elicit thousands of responding messages. Accordingly, expanding ring search can burden a large computer network with hundreds of thousands of messages. If each computer of such a computer network uses an expanding ring search to determine TTL distances to other computers of the computer network, the burden upon the computer network in terms of message traffic is enormous.
What is needed is a mechanism by which computers of a computer network can determine TTL distances to other computers of the computer network without requiring excessive amounts of time or of computer network bandwidth.